package com.leetcode.demo12;

public class Solution {
    public  static String intToRoman(int num) {
        //声明两个数组，列举可能出现的最小不重复对应关系，建立起一一对应的关系
        int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

        StringBuilder sb = new StringBuilder();
        //类似于贪心法找到最高位匹配的数字
        for(int i=0;i<values.length;i++) {
            while(num >= values[i]) {
                num -= values[i];  //把最高位减掉，修正后面继续循环使用的值
                sb.append(strs[i]); //把刚才找到的符合条件的字符加在字符串的后面
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        intToRoman(562);
    }
}
